Logical Physical Clocks
Introduction
Brief History of Time
(とこの論文ではしている。まあケースバイケースでは)kekeho.icon
TrueTimeちゃんと勉強してないけど、多分そうなんだろうkekeho.icon
HLCのアルゴリズム
HLC($ l)は以下の特性を提供する
1. $ e \ \mathsf{hb} \ f \Rightarrow l.e < l.f
3. $ l.eは有限のビット幅で表現される
実際はint64(OSのNTPクロックと同じビット幅) 4. $ l.eは$ pt.eと近い値を取る。$ |l.e - pt.e|が有界
Naive algorithm
任意のイベント$ eに対して、$ l.e \ge pt.eなタイムスタンプを与える
初期化
$ l.j := 0
送信イベント or ローカルイベント$ f
$ l.j := \mathrm{max}(l.j+1, pt.j)
$ l.jをそのイベントのタイムスタンプとする(メッセージにはそれを付ける)
受信イベント of message $ m
$ l.j := \mathrm{max}(l.j+1, l.m+1, pt.j)
$ l.jをそのイベントのタイムスタンプとする
ほぼLamport Clockと一緒kekeho.icon
これで特性1, 2は満たすけど、4は満たされないし、3も満たさない
3を満たさず、どんどんズレが蓄積していく例:
https://scrapbox.io/files/667ecc969d0294001dec84e9.png
HLCアルゴリズム
naive algorithmの$ l.jを、$ l.jと$ c.jに分割
$ l.jはこれまでに学習した$ p.tの最大値を把握するために使うレベル
$ c.jは、$ l.jの値が等しいときにのみ因果関係の更新を捉えるために使用される
送信・ローカルイベント
$ l'.j := l.j
$ l.j := max(l'j, pt.j)
$ \mathsf{If} \ (l.j = l'j) \ \mathsf{then} \ c.j := c.j + 1 \\ \mathsf{Else} \ c.j := 0
イベントのタイムスタンプは$ l.j, c.j
受信イベント of message $ m
$ l'j := l.j
$ l.j := max(l'j, l.m, pt.j)
$ \mathsf{If} \ (l.j = l'j = l.m) \ \mathsf{then} \ c.j := max(c.j, c.m) + 1 \\ \mathsf{Elseif} \ (l.j = l'j) \ \mathsf{then} \ c.j := c.j + 1 \\ \mathsf{Elseif} \ (l.j = l.m) \ \mathsf{then} \ c.j := c.m + 1 \\ \mathsf{Else} \ c.j := 0
イベントのタイムスタンプは$ l.j, c.j
https://scrapbox.io/files/667ed0e952f2a7001d9e2d93.png
要件4を満たすことの証明は論文に書いてある
参考